import java.util.*;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 * https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/
 */
public class Solutions_211 {
    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        boolean res1 = wordDictionary.search("pad");  // output: false
        System.out.println(res1);
        boolean res2 = wordDictionary.search("bad");  // output: true
        System.out.println(res2);
        boolean res3 = wordDictionary.search(".ad");  // output: true
        System.out.println(res3);
        boolean res4 = wordDictionary.search("b..");  // output: true
        System.out.println(res4);
    }
}

/**
 * 解法二：哈希表 + Set 集合（48ms）
 */
class WordDictionary {
    Map<Integer, Set<String>> map = null;
    public WordDictionary() {
        map = new HashMap<>();
    }

    public void addWord(String word) {
        int len = word.length();
        if (!map.containsKey(len)) {
            map.put(len, new HashSet<>());
        }
        Set<String> lenSet = map.get(len);
        lenSet.add(word);
    }

    public boolean search(String word) {
        if (!map.containsKey(word.length())) {
            return false;
        }
        char[] arr = word.toCharArray();
        Set<String> set = map.get(word.length());
        for (String str : set) {
            if (match(str, arr)) {
                return true;
            }
        }
        return false;
    }

    public boolean match(String str, char[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != '.' && str.charAt(i) != arr[i]) {
                return false;
            }
        }
        return true;
    }
}

/**
 * 解法一：字典树 + 递归（55ms）
 */
class WordDictionary2 {
    TrieNode root = null;

    public WordDictionary2() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        char[] arr = word.toCharArray();
        TrieNode cur = root;
        for (char c : arr) {
            if (!cur.containsKey(c)) {
                cur.put(c, new TrieNode());
            }
            cur = cur.get(c);
        }
        cur.setEnd();
    }

    public boolean search(String word) {
        char[] arr = word.toCharArray();
        return match(root, arr, 0);
    }

    public boolean match(TrieNode node, char[] arr, int index) {
        if (index == arr.length) {
            return node.isEnd();
        }
        char c = arr[index];
        if (c == '.') {
            // 可以与 26 个字母匹配
            for (int i = 0; i < 26; i++) {
                char j = (char) (i + 'a');
                TrieNode next = node.get(j);
                // 递归查找
                if (next != null && match(next, arr, index + 1)) {
                    return true;
                }
            }
        } else {
            if (!node.containsKey(c)) {
                return false;
            }
            // 递归查找
            return match(node.get(c), arr, index + 1);
        }
        return false;
    }
}
